package com.algrithom.tree.binarytree;

import java.util.Arrays;
import java.util.List;

import com.common.model.TreeNode;
import com.util.TreeOperUtil;

/**
 * 236. 二叉树的最近公共祖先
 *
 * @author think
 */
public class Solution1 {
    
    private TreeNode<Integer> ans;
    
    public Solution1(){
        this.ans = null;
    }
    
    public static void main(String[] args){
        List<Integer> list = Arrays.asList(3,5,1,6,2,0,8,null,null,7,4);
        TreeNode<Integer> root = TreeOperUtil.createTree(list.toArray(new Integer[]{}),0);
        Solution1 solution1 = new Solution1();
        //        System.out.println(solution1.lowestCommonAncestor(root, new TreeNode<>(5), new TreeNode<>(1)));
        //        System.out.println(solution1.lowestCommonAncestor(root, new TreeNode<>(6), new TreeNode<>(2)));
        System.out.println(solution1.lowestCommonAncestor(root,new TreeNode<>(5),new TreeNode<>(4)));
    }
    
    private boolean dfs(TreeNode<Integer> root,TreeNode<Integer> p,TreeNode<Integer> q){
        if (root == null) {
            return false;
        }
        boolean lson = dfs(root.getLeftChild(),p,q);
        boolean rson = dfs(root.getRightChild(),p,q);
        if ((lson && rson) || ((root.getValue().equals(p.getValue()) || root.getValue().equals(q.getValue())) && (lson || rson))) {
            ans = root;
            return true;
        }
        return lson || rson || root.getValue().equals(p.getValue()) || root.getValue().equals(q.getValue());
    }
    
    public TreeNode<Integer> lowestCommonAncestor(TreeNode<Integer> root,TreeNode<Integer> p,TreeNode<Integer> q){
        this.dfs(root,p,q);
        return this.ans;
    }
}